 #define _CRT_SECURE_NO_WARNINGS 1

class Solution
{
public:
	int numDecodings(string s)
	{
		int n = s.size();
		vector<int> dp(n); // 创建⼀个 dp表 
		// 初始化前两个位置 
		dp[0] = s[0] != '0';
		if (n == 1) return dp[0]; // 处理边界情况 
		if (s[1] <= '9' && s[1] >= '1') dp[1] += dp[0];
		int t = (s[0] - '0') * 10 + s[1] - '0';
		if (t >= 10 && t <= 26) dp[1] += 1;
		// 填表 
		for (int i = 2; i < n; i++)
		{
			// 如果单独编码 
			if (s[i] <= '9' && s[i] >= '1') dp[i] += dp[i - 1];
			// 如果和前⾯的⼀个数联合起来编码 
			int t = (s[i - 1] - '0') * 10 + s[i] - '0';
			if (t >= 10 && t <= 26) dp[i] += dp[i - 2];
		}
		// 返回结果 
		return dp[n - 1];
	}
};